package test4;

import java.util.Arrays;

/**
 * 差分数组
 *
 * @Author Jun jie Yi
 * 2022/5/4 11:27
 */
public class Difference {
    public static void main(String[] args) {
        int[] arr = {2, 1, 4, 3, 5, 6};
        Difference difference = new Difference(arr);
        difference.increment(0,2,3);
        System.out.println(Arrays.toString(difference.result()));
    }

    // 差分数组
    private int[] diff;

    /* 输入一个初始数组，区间操作将在这个数组上进行 */
    public Difference(int[] nums) {
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i,j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }

}
